package leetcode.code2002;

import java.util.HashMap;

import leetcode.helper.MaxDebug;

/**
 * 执行用时：152 ms, 在所有 Java 提交中击败了52.04%的用户

内存消耗：39.2 MB, 在所有 Java 提交中击败了5.59%的用户

通过测试用例：226 / 226
 * @author CaoYu
 * @date 2021年12月5日
 * @description
 */
public class Solution2 extends S2002 {

	@Override
	public int maxProduct(String s) {
		HashMap<String, Integer> dp = new HashMap<>();
		return this.f(s.toCharArray(), 0, new StringBuffer(), new StringBuffer(), dp);
	}

	private int f(char[] charArray, int index, StringBuffer s1, StringBuffer s2, HashMap<String, Integer> dp) {
		if (index == charArray.length) {
			if (dp.containsKey(s1)) {
				return dp.get(s1);
			}
			int len1 = this.longestPalindromeSubseq(s1.toString());
			int len2 = this.longestPalindromeSubseq(s2.toString());
			int ans = len1 * len2;
			dp.put(s1.toString(), ans);
			dp.put(s2.toString(), ans);
			return ans;
		}
		char c = charArray[index];
		int ans1 = this.f(charArray, index + 1, s1, s2.append(c), dp);
		s2.deleteCharAt(s2.length() - 1);
		int ans2 = this.f(charArray, index + 1, s1.append(c), s2, dp);
		s1.deleteCharAt(s1.length() - 1);
		return Math.max(ans1, ans2);
	}

	public int longestPalindromeSubseq(String s) {
		int n = s.length();
		if (n == 0)
			return 0;
		int[][] dp = new int[n][n];
		for (int i = n - 1; i >= 0; i--) {
			dp[i][i] = 1;
			char c1 = s.charAt(i);
			for (int j = i + 1; j < n; j++) {
				char c2 = s.charAt(j);
				if (c1 == c2) {
					dp[i][j] = dp[i + 1][j - 1] + 2;
				} else {
					dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
				}
			}
		}
		return dp[0][n - 1];
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
//		so.debug4();
		MaxDebug.debug14(so);

	}

}
